package 分治;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */


/*
解题思路：
    这题是96题的进化版，这次的主要思路是递归。
        主要是：生成根，生成左子树，生成右子树，拼接。
    还是和96由共同的思想：左子树的节点值的集合为 [1，i−1]，右子树的节点值的集合为 [i+1，n]

  我们定义 helper(start, end) 函数表示当前值的集合为 [start,end]，
  返回序列[start,end] 生成的所有可行的二叉搜索树。
  按照上文的思路，我们考虑枚举[start,end] 中的值 i 为当前二叉搜索树的根，
  那么序列划分为了[start,i−1] 和 [i+1,end] 两部分。
  我们递归调用这两部分，即 helper(start, i - 1) 和 helper(i + 1, end)，
  获得所有可行的左子树和可行的右子树，
  那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。


 */

import java.util.ArrayList;
import java.util.List;


public class 不同的二叉搜索树II_95 {
    public static void main(String[] args) {

        System.out.println(new 不同的二叉搜索树II_95().generateTrees(5));
    }

    public List<TreeNode> generateTrees(int n) {

        if (n == 0) {
            return new ArrayList<>();//如果是0，直接返回一个空的子树
        }
        List<TreeNode> res = helper(1, n);//范围是从1到n
        return res;
    }

    public List<TreeNode> helper(int start, int end) {
        List<TreeNode> res = new ArrayList<>();

        if (start > end) {//边界条件：这种情况就是没有根节点的。
            res.add(null);
            return res;
        }

        for (int i = start; i <= end; i++) {//以i为根节点。
            List<TreeNode> leftChildren = helper(start, i - 1);//获得所有可行的左子树集合：i为根节点的左子树范围[1,i-1]
            List<TreeNode> rightChildren = helper(i + 1, end);//获得所有可行的右子树集合：i为根节点的左子树范围[i+1,end]

            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftChildren) {
                for (TreeNode right : rightChildren) {
                    TreeNode root = new TreeNode(i);//把i作为根节点
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }

            }


        }
        return res;
    }

}

